package algorithm.swordoff;


//  [1,   4,  7, 11, 15],
//  [2,   5,  8, 12, 19],
//  [3,   6,  9, 16, 22],
//  [10, 13, 14, 17, 24],
//  [18, 21, 23, 26, 30]
//]


/**
 *
 * 二维数组的查找
 * 与主站240题相同
 *
 * 这道题的核心是要明白得从右上(大了就往左边找,小了往下)或者左下(大了往上,小了往右)开始搜索
 * 而左上(大了你到底是往上还是往下呢)和右下(理由同)搜索是不行滴
 * 时间复杂度 O(m+n)
 */

public class SQ04 {

    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        int row = 0, col = matrix[0].length-1;

        while (row < matrix.length && col > 0) {
            if (matrix[row][col] == target) return true;
            else if (matrix[row][col] > target) col--; // 大了往左
            else row++; // 小了往下
        }
        return false;
    }

    public static void main(String[] args) {

        int[][] matrix = {{1, 4, 7, 11, 15},
                {2, 5, 8, 12, 19},
                {3, 6, 9, 16, 22},
                {10, 13, 14, 17, 24},
                {18, 21, 23, 26, 30}};
        SQ04 sq04 = new SQ04();
        System.out.println(sq04.findNumberIn2DArray(matrix, 20));
    }

}
